package com.xiaoyu.binaryTree.basic;

import java.util.LinkedList;

/**
 * @program: DS_and_A
 * @description:
 *              1
 *           2    3
 *               4  5
 *
 *
 *
 * @author: YuWenYi
 * @create: 2021-05-13 10:03
 **/
public class BinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1, "大娃");
        root.setLeftNode(new HeroNode(2,"二娃"));

        HeroNode node3 = new HeroNode(3, "三娃");
        root.setRightNode(node3);
        node3.setLeftNode(new HeroNode(4,"四娃"));
        node3.setRightNode(new HeroNode(5,"五娃"));

       /* root.preOrder();
        System.out.println("---");
        root.midOrder();
        System.out.println("---");
        root.postOrder();*/

        //System.out.println(root.postOrderFind(5));
        BinaryTree bTree = new BinaryTree();
        bTree.setRoot(root);

        bTree.layerOrder();
       /* bTree.preOrder();
        bTree.delNode(4);
        System.out.println("==========");
        bTree.preOrder();*/
    }
}


class BinaryTree{
    HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void delNode(int no){
        if (root!=null){
            if (root.getNo() == no){
                root = null;
            }else {
                root.delNode(no);
            }
        }else {
            System.out.println("root为null,无法删除");
        }
    }

    //其他遍历类似
    public void preOrder(){
        if (root!=null){
            root.preOrder();
        }
    }

    //其他查找类似
    public HeroNode preOrderFind(int no){
        if (root != null){
           return root.preOrderFind(no);
        }
        return null;
    }

    public void layerOrder(){
        if (root!=null){
            root.layerOrder();
        }
    }

}

class HeroNode{
    private int no;
    private String name;
    private HeroNode leftNode;
    private HeroNode rightNode;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(HeroNode leftNode) {
        this.leftNode = leftNode;
    }

    public HeroNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(HeroNode rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //在二叉树中,前序,中序,后序三大遍历都是DFS的体现,而层次遍历是BFS的体现

    //层次遍历 --> BFS
    public void layerOrder(){
        LinkedList<HeroNode> queue = new LinkedList<>();
        HeroNode p;
        //当前结点入队列
        queue.offer(this);
        while (!queue.isEmpty()){
            p = queue.poll();
            System.out.println(p);
            if (p.leftNode!=null){
                queue.offer(p.leftNode);
            }
            if (p.rightNode != null){
                queue.offer(p.rightNode);
            }
        }
    }

    //前序遍历
    public void preOrder(){
        //输出当前结点
        System.out.println(this);
        //如果左结点不为空,那么则对左结点进行前序遍历
        if (this.leftNode != null){
            this.leftNode.preOrder();
        }
        //如果右结点不为空,那么则对右结点进行前序遍历
        if (this.rightNode != null){
            this.rightNode.preOrder();
        }
    }

    //中序遍历
    public void midOrder(){
        if (this.leftNode != null){
            this.leftNode.midOrder();
        }
        System.out.println(this);
        if (this.rightNode != null){
            this.rightNode.midOrder();
        }
    }

    //后序遍历
    public void postOrder(){
        if (this.leftNode != null){
            this.leftNode.postOrder();
        }
        if (this.rightNode != null){
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }

    //前序遍历查找:找到了就返回结点,没找到就返回null
    public HeroNode preOrderFind(int no){
        if (no == this.no){
            return this;
        }
        HeroNode resNode = null;
        if (this.leftNode != null){
            resNode = this.leftNode.preOrderFind(no);
        }
        if (resNode != null){
            return resNode;
        }
        //如果右结点不为空,那么则对右结点进行前序遍历
        if (this.rightNode != null){
            resNode = this.rightNode.preOrderFind(no);
        }
        return resNode;
    }
    //中序遍历查找
    public HeroNode midOrderFind(int no){
        HeroNode resNode = null;
        if (this.leftNode != null){
            resNode = this.leftNode.midOrderFind(no);
        }
        if (resNode != null){
            return resNode;
        }
        if (no == this.no){
            return this;
        }
        //如果右结点不为空,那么则对右结点进行前序遍历
        if (this.rightNode != null){
            resNode = this.rightNode.midOrderFind(no);
        }
        return resNode;
    }
    //后序遍历查找
    public HeroNode postOrderFind(int no){
        HeroNode resNode = null;
        if (this.leftNode != null){
            resNode = this.leftNode.postOrderFind(no);
        }
        if (resNode != null){
            return resNode;
        }
        //如果右结点不为空,那么则对右结点进行前序遍历
        if (this.rightNode != null){
            resNode = this.rightNode.postOrderFind(no);
        }
        if (resNode != null){
            return resNode;
        }

        if (no == this.no){
            return this;
        }
        return null;
    }

    //删除结点
    //1.如果删除的节点是叶子节点,则删除该节点
    //2.如果删除的节点是非叶子节点,则删除该子树
    /*
        前提:
        root如果为空,就直接返回,如果root结点的id即为要删除的id,那么就删除root,否则才进入下面的递归删除
        思路:
        1。因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点。
        2。如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left = null;并且就返回(结束递归删除)
        3。如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
        4。如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除
        5。如果第4步也没有删除结点,则应当向右子树进行递归删除。
    */
    public void delNode(int no){
        if (this.leftNode != null && this.leftNode.getNo() == no){
     /*       if (this.leftNode.leftNode != null && this.leftNode.rightNode==null){
                this.leftNode.leftNode = null;
            }else if (this.leftNode.leftNode == null && this.leftNode.rightNode!=null){
                this.leftNode.rightNode = null;
            }else if (this.leftNode.leftNode != null && this.leftNode.rightNode!=null){
                this.leftNode.rightNode = null;
            }*/
            this.leftNode = null;
            return;  //用它来提前结束递归,即如果找到了删除的元素,删除后就立马退出递归
        }
        if (this.rightNode != null && this.rightNode.getNo() == no){
            this.rightNode = null;
            return;
        }
        //进入该结点的左子树中进行寻找
        if (this.leftNode != null){
            this.leftNode.delNode(no);
        }
        //左子树如果没找到就进入右子树进行寻找
        if (this.rightNode != null){
            this.rightNode.delNode(no);
        }
    }

}